/*
 * 8.4
 * Write a method to compute all permutations of a string.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;

/* XXX: time complexity is O(n!). */

/* recursive version */
void permutation(char *str, int i)
{
    if (str[i+1] == '\0') {
        printf("%s\n", str);
        return;
    }
    for (int k = i; str[k]; k++) {
        std::swap(str[i], str[k]);
        permutation(str, i+1);
        std::swap(str[i], str[k]);
    }
}

/* recursive version, detecting repeat elements. */
void permutation2(char *str, int i)
{
    if (str[i+1] == '\0') {
        printf("%s\n", str);
        return;
    }
    for (int k = i; str[k]; k++) {
        bool find = false;
        for (int kk = i; kk < k; kk++) {
            if (str[kk] == str[k]) {
                find = true;
                break;
            }
        }
        if (!find) {
            std::swap(str[i], str[k]);
            permutation2(str, i+1);
            std::swap(str[i], str[k]);
        }
    }
}

/* std::next_permutation() */
void std_permutation(char *str)
{
    int len = strlen(str);
    std::sort(str, str+len); /* required */
    do {
        printf("%s\n", str);
    } while (std::next_permutation(str, str+len));
}

int main()
{
    char str[] = "aaa";
    permutation2(str, 0);
    return 0;
}
